Methods for performing searches of encrypted data that do not compromise the confidentiality of the encrypted data are known to the art. For example, in one common configuration a server computing device stores a large number of encrypted data files with an associated encrypted search index. One or more client computing devices make search requests to the server using encrypted representations of search keyword terms. Symmetric Searchable Encryption (SSE) is one method for performing searches in an encrypted search index that enables a client computing device that has access to a symmetric cryptographic key to perform searches for specific terms in the encrypted search index that is stored on the server. The server, however, only receives the encrypted search terms and cannot identify the content of the search terms based on the communications that are received from the client because the server does not have access to the (secret) cryptographic key required to decrypt the search terms.
Existing searchable encryption systems enable a client to search for a specific term or “keyword” in an encrypted search index. However, the existing searchable encryption systems have difficulty in ensuring that the results returned from the server are actually valid. For example, even though an untrusted server cannot identify the contents of an encrypted search keyword or the contents of encrypted files, a server that has been compromised by an attacker may simply return false results to the client in response to a search. The results may be completely incorrect, which the client would likely identify after receiving one or more clearly erroneous search results. However, in a more subtle attack the server may return partially correct results to the client that may convince the client that the server is operating normally when the server has in fact been compromised. Consequently, improvements to methods and systems for performing searches in encrypted data that enable a client to verify that the search results returned from a server are both accurate and complete would be beneficial.